#pragma once
#include <iostream>
#include <assert.h>
#include <thread>
#include <mutex>
#include <algorithm>
typedef size_t PAGE_ID;
// 小于等于MAX_BYTES，就找thread cache申请
// 大于MAX_BYTES，就直接找page cache或者系统堆申请
static const size_t MAX_BYTES = 256 * 1024;
// thread cache和central cache自由链表哈希桶的表大小
static const size_t NFREELISTS = 208;
class FreeList
{
public:
    static void *&NextObj(void *obj)
    {
        return *(void **)obj;
    }

public:
    void Push(void *obj)
    {
        // 头插
        assert(obj);
        NextObj(obj) = _freeList;
        _freeList = obj;
    }
    void PushRange(void *start, void *end)
    {
        NextObj(end) = _freeList;
        _freeList = start;
    }
    void *Pop()
    {
        // 头删
        assert(_freeList);
        void *obj = _freeList;
        _freeList = NextObj(obj);
        return obj;
    }
    bool Empty()
    {
        return _freeList == nullptr;
    }
    size_t &MaxSize()
    {
        return _maxSize;
    }

private:
    void *_freeList = nullptr;
    size_t _maxSize = 1;
};

// 计算对象大小的对齐映射规则

class SizeClass
{

    //[1,128] 8bytes对齐 freeList[0,16)
    //[128+1,1024] 16bytes对齐 freeList[16,72)
    //[1024+1,8*1024] 128bytes对齐 freeList[72,128)
    //[8*1024+1,64*1024] 1024bytes对齐 freeList[128,184)
    //[64*1024+1,256*1024] 8*1024bytes对齐 freeList[184,208)
    static inline size_t _Roundup(size_t size, size_t alignNum) // 计算size以alignNum为对齐数后对齐的值
    {
        return (size + alignNum - 1) & ~(alignNum - 1);
    }
    static inline size_t _Index(size_t bytes, size_t alignShift) // 计算bytes以2^alignShift对应数的哈希桶对应的下标
    {
        return (bytes + (1 << alignShift) - 1 >> alignShift) - 1;
    }

public:
    static inline size_t RoundUp(size_t size) // 计算出size对齐后的大小
    {
        if (size <= 128)
        {
            return _Roundup(size, 8);
        }
        else if (size <= 1024)
        {
            return _Roundup(size, 16);
        }
        else if (size <= 8 * 1024)
        {
            return _Roundup(size, 128);
        }
        else if (size <= 64 * 1024)
        {
            return _Roundup(size, 1024);
        }
        else if (size <= 256 * 1024)
        {
            return _Roundup(size, 8 * 1024);
        }
        else
        {
            // 不可能走到这
            assert(false);
            return -1;
        }
    }
    // 获取对应哈希桶的下标
    static inline size_t Index(size_t bytes)
    {
        // 每个区间有多少个自由链表
        static int groupArray[4] = {16, 56, 56, 56};
        if (bytes <= 128)
        {
            return _Index(bytes, 3);
        }
        else if (bytes <= 1024)
        {
            return groupArray[0] + _Index(bytes - 128, 4);
        }
        else if (bytes <= 8 * 1024)
        {
            return groupArray[0] + groupArray[1] + _Index(bytes - 1024, 7);
        }
        else if (bytes <= 64 * 1024)
        {
            return groupArray[0] + groupArray[1] + groupArray[2] + _Index(bytes - 8 * 1024, 10);
        }
        else if (bytes <= 256 * 1024)
        {
            return groupArray[0] + groupArray[1] + groupArray[2] + groupArray[3] + _Index(bytes - 64 * 1024, 13);
        }
        else
        {
            assert(false);
            return -1;
        }
    }
    // thread_cache一次从central cache获取对象的上限
    static size_t NumMoveSize(size_t size)
    {
        assert(size > 0);
        size_t num = MAX_BYTES / size;
        if (num < 2)
        {
            num = 2;
        }
        if (num > 512)
        {
            num = 512;
        }
        return num;
    }
};

struct Span
{
    PAGE_ID _pageId = 0; // 大块内存起始页的页号
    size_t _n = 0;       // 页的数量
    Span *_next = nullptr;
    Span *_prev = nullptr;
    size_t _useCount = 0;      // 切好的小块内存，被分配给thread cache的个数
    void *_freeList = nullptr; // 切好的小块内存的自由链表
};

class SpanList
{
public:
    SpanList()
    {
        _head = new Span;
        _head->_next = _head;
        _head->_prev = _head;
    }
    void Insert(Span *pos, Span *newSpan)
    {
        assert(pos);
        assert(newSpan);
        Span *prev = pos->_prev;
        prev->_next = newSpan;
        newSpan->_next = pos;
        pos->_prev = newSpan;
        newSpan->_prev = prev;
    }
    void Erase(Span *pos)
    {
        assert(pos);
        assert(pos != _head);
        Span *prev = pos->_prev;
        Span *next = pos->_next;
        prev->_next = next;
        next->_prev = prev;
    }

private:
    Span *_head;

public:
    std::mutex _mutex; // 桶锁
};